package _01_动态数组;

import java.util.Arrays;

public class _4_寻找两个正序数组的中位数 {

    public static void main(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] newAry = new int[len1 + len2];
        int point1 = len1 - 1;
        int point2 = len2 - 1;
        int storeIndex = newAry.length - 1;
        while (point1 >= 0 && point2 >= 0) {
            if (nums1[point1] > nums2[point2]) {
                newAry[storeIndex--] = nums1[point1--];
            } else {
                newAry[storeIndex--] = nums2[point2--];
            }
        }
        // 判断谁先结束
        if (point2 > point1) {
            // point1先结束
            System.arraycopy(nums2, 0, newAry, 0, point2 + 1);
        } else if (point1 > point2){
            System.arraycopy(nums1, 0, newAry, 0, point1 + 1);
        }

        // 计算中位数
        if ((newAry.length & 1) == 1) {
            // 奇数
            return newAry[newAry.length >> 1];
        } else {
            // 偶数
            return (newAry[newAry.length >> 1] + newAry[(newAry.length >> 1) - 1]) / 2.0;
        }
    }

}
